package homework;

@SuppressWarnings("all")
// 求数组中第k小的元素
public class F4 {

    public static void main(String[] args) {

        int[] data = {1, 245, 7657, 34, 6, 2, 53, 5};
        System.out.println(t1(data, 0, data.length - 1, 3));
    }

    public static int t1(int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        if (i < j) {
            int p = nums[i];
            while (left != right) {
                while (right > left && nums[right] >= p) {
                    right--;
                }
                nums[left] = nums[right];
                while (right > left && nums[left] <= p) {
                    left++;
                }
                nums[right] = nums[left];
            }
            // 将中枢放入
            nums[left] = p;
            if (k - 1 == left) {
                return nums[left];
            } else if (k - 1 < left) {
                return t1(nums, i, left - 1, k);
            } else {
                return t1(nums, left + 1, j, k);
            }

        } else if (i == j && i == k - 1) {
            return nums[k - 1];
        }
        return -1;
    }
}
